package tianhao.luo.algorithm;

import java.util.Arrays;

/**
 * 冒泡排序
 *
 * @author: tianhao.luo@hand-china.com 2021/6/17  21:32
 */
public class BubbleSort {

    private int[] array;

    public BubbleSort(int[] array) {
        this.array = array;
    }

    /**
     * 排序算法
     */
    public void sort(){
        /*
        推演思路
        // 第一趟排序
        for (int i = 0; i < array.length - 1; i++) {
            int temp =0;
            // 如果array[i]>array[i+1],就进行交换
            if (array[i]>array[i+1]){
                temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }

        // 第二趟排序
        for (int i = 0; i < array.length - 1-1; i++) {
            int temp =0;
            // 如果array[i]>array[i+1],就进行交换
            if (array[i]>array[i+1]){
                temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }

        // 第三趟排序
        for (int i = 0; i < array.length - 1-2; i++) {
            int temp =0;
            // 如果array[i]>array[i+1],就进行交换
            if (array[i]>array[i+1]){
                temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }

        // 第四趟排序
        for (int i = 0; i < array.length - 1-3; i++) {
            int temp =0;
            // 如果array[i]>array[i+1],就进行交换
            if (array[i]>array[i+1]){
                temp = array[i];
                array[i] = array[i+1];
                array[i+1] = temp;
            }
        }

        发现上面的四趟排序,发生变化的就只是for循环中的循环控制条件;元素比较的循环的控制条件是array.length-趟数;
        又因为循环的趟数的控制条件是array.length-1,可以利用趟数的循环来控制元素比较的循环
        */

        // 冒泡排序的时间复杂度就是O(n^2)
        // 1.一共进行数组的大小-1趟循环
        for (int i = 0; i < array.length-1; i++) {
            // 这个j循环,就是用来比较元素是否需要交换的
            // 外层i循环,就是用来控制趟数和比较次数的

            // 优化,如果本趟比较之后,发现没有元素发生交换,表示已经是完全有序的了
            int count =0;
            for (int j = 0; j < array.length-1-i; j++) {
                // 如果array[j]>array[j+1],就进行交换
                if (array[j]>array[j+1]){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                    count++;
                }
            }
            // 优化,count为0,表示一次交换都没有发生
            if (count==0){
                break;
            }
        }
    }


    /**
     * 打印
     */
    public void print(){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
    }
}
